import java.util.Arrays;

/*
 * @lc app=leetcode.cn id=279 lang=java
 *
 * [279] 完全平方数
 */

// @lc code=start
class Solution {
    public int numSquares(int n) {
        //完全背包，求背包装满所需物品最少数
        int[] dp=new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0]=0;
        for(int i=1;i*i<=n;i++){//物品这里就是完全数i*i
            for(int j=i*i;j<=n;j++){//遍历背包
                if(dp[j-i*i]!=Integer.MAX_VALUE){
                    dp[j]=Math.min(dp[j],dp[j-i*i]+1);
                }
            }
        }
        return dp[n]==Integer.MAX_VALUE?-1:dp[n];
  

    }
}
// @lc code=end

